The classical and most used lossless data compression algorithms are based on Lempel-Ziv (LZ) seminal papers from the 70s. LZ compression is based on dictionary coding, where the amount of data to be stored is reduced by replacing the data with dictionary references. The dictionary may be external to the data being coded or internal to the data. When the dictionary is external, then both the encoder and the decoder should have access to the same dictionary. An internal dictionary means that the content of the current decoded data may be used as a dynamic dictionary, also called “sliding window” dictionary. The current compression algorithms generate a stream of tokens that mixes references to entries in dictionaries and embedded data.
LZ compression forms the base for multiple implementation variants that differ in their dictionary complexity, encoding scheme, speed, memory resources yielding variant compression efficiency. The most popular variant corresponds to the sliding window approach that produces an encoded stream composed of interleaved combination of dictionary values (data values) and dictionary references (position and length).